from typing import List


class DSU:
    def __init__(self, n: int):
        self._n = n
        self._array = [i for i in range(n)]
        self._size = [1] * n
        self._group_num = n

    def find(self, i: int) -> int:
        """查询i所在的连通分支:O(1)"""
        if self._array[i] != i:
            self._array[i] = self.find(self._array[i])
        return self._array[i]

    def union(self, i: int, j: int) -> bool:
        """合并i和j所属的连通分支:O(1)"""
        i, j = self.find(i), self.find(j)
        if i != j:
            self._group_num -= 1
            if self._size[i] >= self._size[j]:
                self._array[j] = i
                self._size[i] += self._size[j]
            else:
                self._array[i] = j
                self._size[j] += self._size[i]
            return True
        else:
            return False

    def is_connected(self, i: int, j: int) -> bool:
        return self.find(i) == self.find(j)

    @property
    def array(self) -> list:
        return self._array


class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        size = row * col

        # 初始化并查集:size=最上面一行的上方;size+1=最下面一行的下方
        dsu = DSU(size + 2)

        land = [[False] * col for _ in range(row)]

        above = size
        bottom = size + 1

        # 从后向前遍历
        for i1 in range(size - 1, -1, -1):
            x, y = cells[i1]

            idx1 = (x - 1) * col + (y - 1)

            # print(i1, "-", [x, y], "->", idx1)

            # 处理最上面一行的情况
            if x == 1:
                dsu.union(above, idx1)

            # 处理最下面一行的情况
            if x == row:
                dsu.union(bottom, idx1)

            # 处理周围相连的情况
            if x > 1 and land[x - 2][y - 1] is True:
                idx2 = (x - 2) * col + (y - 1)
                dsu.union(idx1, idx2)
            if y > 1 and land[x - 1][y - 2] is True:
                idx2 = (x - 1) * col + (y - 2)
                dsu.union(idx1, idx2)
            if x < row and land[x][y - 1] is True:
                idx2 = x * col + (y - 1)
                dsu.union(idx1, idx2)
            if y < col and land[x - 1][y] is True:
                idx2 = (x - 1) * col + y
                dsu.union(idx1, idx2)

            # 将当前位置定义为陆地
            land[x - 1][y - 1] = True

            if dsu.find(above) == dsu.find(bottom):
                return i1


if __name__ == "__main__":
    # 2
    print(Solution().latestDayToCross(row=2, col=2,
                                      cells=[[1, 1], [2, 1], [1, 2], [2, 2]]))

    # 1
    print(Solution().latestDayToCross(row=2, col=2,
                                      cells=[[1, 1], [1, 2], [2, 1], [2, 2]]))

    # 3
    print(Solution().latestDayToCross(row=3, col=3,
                                      cells=[[1, 2], [2, 1], [3, 3], [2, 2], [1, 1], [1, 3], [2, 3], [3, 2], [3, 1]]))
